package hot100.logos11To20;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @author logos
 * date 2025/7/10 12:01
 * @version v1.0
 * @Package hot100
 */
public class logos14 {

    /**
     * 14.合并区间
     * https://leetcode.cn/problems/merge-intervals/?envType=study-plan-v2&envId=top-100-liked
     */

    class Solution {
        public int[][] merge(int[][] intervals) {
            Arrays.sort(intervals, (x, y) -> x[0] - y[0]);
            int n = intervals.length;
            int preEnd = intervals[0][1];
            int preIndex = 0;
            ArrayList<int[]> ans = new ArrayList<>();
            for (int i = 1; i < n; i++) {
                if (intervals[i][0] <= preEnd) {
                    preEnd = Math.max(preEnd, intervals[i][1]);
                } else {
                    ans.add(new int[] { intervals[preIndex][0], preEnd });
                    preEnd = intervals[i][1];
                    preIndex = i;
                }
            }
            ans.add(new int[] { intervals[preIndex][0], preEnd });
            return ans.toArray(new int[ans.size()][]);
        }
    }
}
